Forum:Buchholz's FS system
For a while I thought that the Wainer hierarchy (\(\mu = \varepsilon_0 + 1\)) was the largest fundamental sequence system known to be increasing in FGH -- that is, for all \(\alpha < \beta < \mu\), \(f_\alpha\) is eventually dominated by \(f_\beta\). Wojowu pointed out to me that, in the paper introducing his hydra, Buchholz created a fundamental sequence system with \(\mu = \text{TFB}\) and proved that it is increasing (lemma 3.6d). A few questions remain before this hierarchy is useful to us. For example, is it an extension of the Wainer hierarchy? -- ve 18:35, August 17, 2015 (UTC) : I didn't get into details of all the definitions, but Buchholz's FGH is indexed not with ordinals themselves, but rather terms, which are just notations for ordinals. One thing which I'm not sure about is whether one ordinal can be represented with multiple different terms, and if the answer is yes, whether choosing different term for the same ordinal might lead to a different function. LittlePeng9 (talk) 19:17, August 17, 2015 (UTC) :: Right you are. At this point that we're all lazily waiting for one of us to work through the paper. -- ve 04:33, August 19, 2015 (UTC) :We can convert from terms to ordinals by restricting terms to "normal forms". For that we need to do two things: we require that any term of the form \((\alpha_1, \alpha_2, \ldots, \alpha_n)\) satisfies \(\alpha_1 \ge \alpha_2 \ge \ldots \ge \alpha_n\). This also means we need to change the notion of addition from concatenation to the normal definition of addition for ordinals. Secondly, we need to restrict which terms of the form \(D_u v\) are allowed, so that no ordinal occurs in proper form more than once. I believe this is reasonably doable, but I would need to think about exactly how to do it. :Fortunately, there is no problem for ordinals up to \(\varepsilon_0\), since for that we can use just \(D_0\), and then we just need the first rule above to get normal forms. So we do get fundamental sequences; they aren't the same as the FSes in what we call the Wainer hierarchy, because Buchholz uses the rule \(D_u(b+1)n = D_u(b) (n+1)\), whereas we have defined the Wainer hierarchy using the rule \(\omega^{b+1}n = \omega^b n\). But if we replace the "n+1" in the former rule with "n", then we do indeed get the same FSes as the Wainer hierarchy. :For higher ordinals, there is an interesting quirk: if we have \(D_v (b)\) where \(dom(b) = T_u\) and \(v \le u < \omega\), then \(dom(D_v(b)) = \mathbb{N}\) and \(D_v(b)n = D_v (b[D_u(b1)])\). But \( D_v (b[D_u(b1)])\) is a constant ordinal, so that isn't a fundamental sequence at all! There are two things we could do to deal with this: one is to treat \( D_v (b[D_u(b1)])\) as an intermediate calculation, and to consider the actual fundamental sequence of \(D_v(b)\) to be the fundamental sequence of \( D_v (b[D_u(b1)])\). This will get us proper increasing sequences, but the limits of these increasing sequences are less than what we would expect the starting ordinal to be. For example, \(D_0(D_1(0))\) would naturally be the smallest ordinal not describable by \(D_0\) alone, which would be \(\varepsilon_0\), but using the above rule we get \(D_0(D_1(0))n = D_0(D_1(0)[D_0(D_1(0)1)]) = D_0(D_0(1)) = \omega^\omega\). So we have to set certain terms equal to smaller ordinals than we would expect; however, since Buchholz proves that the Hardy hierarchy for his system goes beyond the provably recursive functions of \(\Pi^1_1-CA+BI\), we would expect that the ordinals still go up to \(\psi_0(\varepsilon_{\Omega_\omega+1})\). :Alternatively, we could redefine the fundamental sequence for the case above to by the following rule: set \(a_0 = b0\) (or b1 or anything reasonable) and \(a_{n+1} = bD_u(a_n)\). Then set \(D_v(b)n = D_v(a_n)\). This will give us a proper fundamental sequence, and this time the limit is what we expect; for example, we get \(D_0(D_1(0))n = D_0(D_0(\ldots(D_0(0))\ldots)) = \omega \uparrow \uparrow n\). Deedlit11 (talk) 06:44, August 19, 2015 (UTC) :By the way, we can insure that FGH is always increasing for any system of FSes by making a small change to the definition: instead of \(f_\alpha(n) = f_{\alphan}(n)\) for limit ordinals \(\alpha\), we define \(f_\alpha(n) = \sup_{m \le n} (f_{\alpham}(n))\). One can prove that if we use this rule, then if \(\alpha < \beta\) then \(f_\alpha\) is eventually dominated by \(f_\beta\). Deedlit11 (talk) 22:55, August 24, 2015 (UTC)